package Algorithm.LinkedListProblem;

/**
 * @Author cj
 * @Date 2021/12/28 20:11
 */
public class getIntersectNode {

    static class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    // 判断有无环
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 第一次相遇
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                // 第二次相遇
                return fast;
            }
        }
        // 跳出来说明无环
        return null;
    }

    // 判断无环链表相交节点
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int num = 0;
        Node cur1 = head1, cur2 = head2;
        while (cur1.next != null) {
            num++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            num--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) {
            return null;
        }
        // 谁长谁先走
        cur1 = num >=0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        num = Math.abs(num);
        while (num-- > 0) {
            cur1 = cur1.next;
        }
        // 同时走
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    // 判断有环链表相交节点
    public static Node bothLoop(Node head1, Node head2) {
        Node cur1 = head1, cur2 = head2;
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if (loop1 == loop2) {
            int num = 0;
            while (cur1 != loop1) {
                num++;
                cur1 = cur1.next;
            }
            while (cur2 != loop1) {
                num--;
                cur2 = cur2.next;
            }
            // 谁长谁先走
            cur1 = num >= 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            num = Math.abs(num);
            while (num-- > 0) {
                cur1 = cur1.next;
            }
            // 同时走
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            cur1 = loop1;
            while (cur1.next != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

    // 返回两个链表相交节点（总方法）
    public static Node getIntersectNode1(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = getLoopNode(head1);
        Node cur2 = getLoopNode(head2);
        if (cur1 == null && cur2 == null) { // 两个无环
            return noLoop(head1, head2);
        }
        if (cur1 != null && cur2 != null){ // 两个有环
            return bothLoop(head1, head2);
        }
        return null;
    }
}
